#include <stdio.h>
/* https://c.biancheng.net/view/3439.html */

//自定义的输出函数
void printSort(int a[], int n, int i) {
    printf("%d:", i);
    for(int j = 0; j < n; j++) {
        printf("%d ", a[j]);
    }
    printf("\n");
}

//直接插入排序函数
void InsertSort(int a[], int n) {
    for(int i = 1; i < n; i++) {
        //若第 i 个元素大于 i-1 元素则直接插入；反之，需要找到适当的插入位置后在插入。
        if(a[i] < a[i-1]) {
            int j = i - 1;
            int x = a[i];
            while (j > -1 && x < a[j])
            {
                /* code */
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = x;
        }
        //打印每次排序后的结果
        printSort(a, n, i);
    }
}

int main(int argc, char * argv[]) {
    int a[8] = {3, 1, 7, 5, 2, 4, 9, 6};
    InsertSort(a, 8);
    return 0;
}